public class Solution115 {
    public int numDistinct(String s, String t) {
        int m = s.length();
        int n = t.length();
        if (m < n) {
            return 0;
        }
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for (int i = 1; i < m + 1; i++) {
            for (int j = Math.min(i, n); j > 0; j--) {
                dp[j] += (s.charAt(i - 1) == t.charAt(j - 1) ? dp[j - 1] : 0);
            }
        }
        return dp[n];
    }
}
